package sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {12, 32, 83, 38, 28, 9, 100, 1234, 321};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int arr[]) {
        // 最大数位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = arr[i] > max ? arr[i] : max;
        }
        int maxLength = (max + "").length();

        // 二维数组，存放
        int ton[][] = new int[10][arr.length];
        int tonCount[] = new int[10]; // 10个桶存的数量

        // 循环 maxlength 个位数
        for (int i = 0, divisor = 1; i < maxLength; i++, divisor *= 10) {
            // 数组的每个
            for (int j = 0; j < arr.length; j++) {
                // 放哪个桶
                int x = (arr[j] / divisor) % 10;
                ton[x][tonCount[x]] = arr[j];
                tonCount[x] ++;
            }
            // 桶中的数取回来
            int index = 0;
            for (int a = 0; a < 10; a++) {
                for (int b = 0; b < tonCount[a]; b++) {
                    arr[index++] = ton[a][b];
                }
                // 桶存的数量清空
                tonCount[a] = 0;
            }
        }

    }
}
